1482. 制作 m 束花所需的最少天数

给你一个整数数组 bloomDay，以及两个整数 m 和 k 。

现需要制作 m 束花。制作花束时，需要使用花园中相邻的 k 朵花。

花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好可以用于一束花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

示例 1：

输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _]   // 只能制作 1 束花
2 天后：[x, _, _, _, x]   // 只能制作 2 束花
3 天后：[x, _, x, _, x]   // 可以制作 3 束花，答案为 3

示例 2：

输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
输出：-1
解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。

示例 3：

输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出：12
解释：要制作 2 束花，每束需要 3 朵。
花园在 7 天后和 12 天后的情况如下：
7 天后：[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
12 天后：[x, x, x, x, x, x, x]
显然，我们可以用不同的方式制作两束花。

示例 4：

输入：bloomDay = [1000000000,1000000000], m = 1, k = 1
输出：1000000000
解释：需要等 1000000000 天才能采到花来制作花束

示例 5：

输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
输出：9

提示：

bloomDay.length == n
1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <= 10^6
1 <= k <= n

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets

思路及分析

题目分析

一个整数数组bloomDay，存储着每朵花开的时间
花朵的总数是bloomDay数组长度
m*k是制作m束花需要的花朵总数
制作一束花的规则是连续开花，即在bloomDay中是连续的
不能摘到 m 束花返回 -1

求什么？

摘m束花需要的时间
所需时间最少

步骤分析

何时返回-1

制作m束花需要的花朵数小于全开花的花朵总数

即，m*k < len(bloomDay)时必定不能摘到m束花

确定二分查找范围

至少开一朵花，即时间最少min(bloomDay)
全部开花，时间最多max(bloomDay)

二分范围是[min(bloomDay), max(bloomDay)]

left, right = min(bloomDay), max(bloomDay)

寻找二分查找条件

不知道怎么找查找条件？可以试着从『二分查找范围』内取出一个值mid，想一想我拿到这个mid再根据题意能求出什么？

很明显，如果我们确定了制作的时间（mid），那么我们就能求出在这个时间内能做出多少束花

也就是 在mid时间内做出的数量与 m 的比较

在mid时间内做出的mid_m束花，关于如何计算出mid_m我们可以先不考虑

mid_m > m

表面含义	实际含义	接下来做什么	确定下一次范围
花做的太多	时间太多（mid太大）	减少时间	[left, mid]

mid_m < m

表面含义	实际含义	接下来做什么	确定下一次范围
花做的太少	时间太少（mid太小）	增加时间	[mid+1, right]

mid_m == m

表面含义	实际含义	接下来做什么	确定下一次范围
做的一样多	时间刚够或时间多了	可能减少时间	[left, mid]

计算`mid`时间能做出多少束花

在这一步有两个规则

bloomDay元素小于或等于mid的花才能摘
能摘的花必须是连续的，连续的数量等于k

第一时间想到的是『遍历』

mid_m表示mid时间内制作的总数，初始化为0

x表示连续摘取的个数

当x等于k时表示可连续摘取，mid_m+1并x=0
当x小于k时，而下一朵花还未开花则不连续，x=0

用代码实现

    def helper(self, bloomDay, mid, k):
        """
        求时间为mid时，能够制作多少束花
        """
        mid_m = 0 
        x = 0 # 已连续的个数
        for t in bloomDay:
            if t <= mid:
                # 当前花朵已开
                x += 1
                # 如果x与k，相等表示连续满足
                if x == k:
                    # 可制作的花束 + 1
                    mid_m += 1
                    # 将x置为0，重新开始计算连续数
                    x = 0
            else:
                # 未开花朵
                x = 0
        return mid_m

完整代码

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        left, right = min(bloomDay), max(bloomDay)
        if len(bloomDay) < m * k:
            return -1
        while left < right:
            mid = (left + right) >> 1
            mid_m = self.helper(bloomDay, mid, k)
            if mid_m < m:
                left = mid + 1
            else:
                right = mid
        return left

    def helper(self, bloomDay, mid, k):
        """
        求时间为mid时，能够制作多少束花
        """
        mid_m = 0 
        x = 0 # 已连续的个数
        for t in bloomDay:
            if t <= mid:
                # 当前花朵已开
                x += 1
                # 如果x与k，相等表示连续满足
                if x == k:
                    # 可制作的花束 + 1
                    mid_m += 1
                    # 将x置为0，重新开始计算连续数
                    x = 0
            else:
                # 未开花朵
                x = 0
        return mid_m

个人小结

我做题量不咋多，对于二分查找类题目有点自己的理解，欢迎大家讨论共进步

找二分查找范围
确定二分条件

如果是复杂条件，先不要去考虑，你就考虑从二分范围内取的值能求出什么，求出的值和谁（不变量）比较

处理边界，确定下一次二分范围

根据题目慢慢想，可以像我上面那样画一个表格，从表面的大小关系推出其实际含义

如果是复杂条件判断，最后一步再来做这个

相似题目推荐

关于更多『二分查找』的题目，推荐@liweiwei1419带佬的使用「力扣」学习算法与数据结构

二分查找是免费的，相信对大家很有帮助！